
\prob{0091}{次方和整除}

证明：对于任意非负整数$n$，$5 \mid 1^n + 2^n + 3^n + 4^n$，当且仅当$4 \nmid n$。
\problabels{yellow/数论, green/证明题}

\subsection{周期性}

注意到
\begin{align*}
  1^{n + 4} \equiv 1\cdot1^n &\equiv 1^n \pmod 5 \\
  2^{n + 4} \equiv 16\cdot2^n &\equiv 2^n \pmod 5 \\
  3^{n + 4} \equiv 81\cdot3^n &\equiv 3^n \pmod 5 \\
  4^{n + 4} \equiv 256\cdot4^n &\equiv 4^n \pmod 5 \\
\end{align*}
于是有
\[ 1^{n + 4} + 2^{n + 4} + 3^{n + 4} + 4^{n + 4} \equiv 1^n + 2^n + 3^n + 4^n \]
故只需要考虑$n = 0, 1, 2, 3$的情况，其它情况由周期性推知：
\begin{align*}
  1^0 + 2^0 + 3^0 + 4^0 = 4 &\equiv 4 \pmod 5 \\
  1^1 + 2^1 + 3^1 + 4^1 = 10 &\equiv 0 \pmod 5 \\
  1^2 + 2^2 + 3^2 + 4^2 = 30 &\equiv 0 \pmod 5 \\
  1^3 + 2^3 + 3^3 + 4^3 = 100 &\equiv 0 \pmod 5 \\
\end{align*}
可见$5 \mid 1^n + 2^n + 3^n + 4^n$，当且仅当$4 \nmid n$。证毕。
